# -*- coding: utf-8 -*-

# 问题描述：
# 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

# 示例 1：
# 输入: "babad"
# 输出: "bab"
# 注意: "aba"也是一个有效答案。

# 示例 2：
# 输入: "cbbd"
# 输出: "bb"

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        #有中心元素
        max_length = 0;
        max_center = 0;
        index = 0;
        while index < len(s) - 1:
            length = 1;
            while index - length >= 0 and index + length < len(s) and s[index - length] == s[index + length]:
                length = length + 1;
            if length != 1 and length - 1 > max_length:
                max_length = length - 1;
                max_center = index;
            index = index + 1;

        #无中心
        index = 0;
        non_center_max_length = 0;
        non_max_center = 0;
        while index < len(s):
            length = 0;
            while index - length >= 0 and index + 1 + length < len(s) and s[index - length] == s[index + 1 + length]:
                length = length + 1;
            if length != 0 and length > non_center_max_length:
                non_center_max_length = length;
                non_max_center = (index + index + 1) / 2.0;
            index = index + 1;

        if 2 * max_length + 1 > 2 * non_center_max_length:
            return s[max_center - max_length: max_center + max_length + 1];
        else:
            return s[int(non_max_center) - (non_center_max_length - 1): int(non_max_center) + 1 + (non_center_max_length - 1) + 1];








# 阅读官方提供的答案
# 以上方案和官方提供的解题思路相同 Yeah!

# 官方提供的一个错误的解题思路
# 错误的思路经常能把人的整个思路都带偏，导致最终所有努力都化为流水
# 这里着重理解一下错误思路，错在什么地方，以避免遇到这种问题
#   反转S，使之变成S′找到S和S′之间最长的公共子串，这也必然是最长的回文子串
# 回文要求的是颠倒并且紧挨着，当时上面的解题思路没有考虑到紧挨着的情况
# eg:
# S = "abacdfgdcaba";
# S′= "abacdgfdcaba";
# 公共字串是"abacd"但并不是回文字串

# 官方答案2：Manacher算法
# https://articles.leetcode.com/longest-palindromic-substring-part-ii/
# 具体的思路是在上方的解法的一种改进，具体的原理是通过已找出的回文字符串，推测出后面字符串
# 时间复杂度更低为 O(n)

# 解题思路
# 1、在字符串中加入"#"避免掉回文字符长度是奇数还是偶数的问题
# eg: aba       abba
#     a#b#a     a#b#b#a
# 2、使用已经查找到的回文长度推测下一个字符的回文长度
# eg: babcbabcbaccba
#     ^b#a#b#c#b#a#b#c#b#a#c#c#b#a$
#     000201060109
# 以当前这个状态为例一直'a'周围有长度为9的回文字符串，也即如下情况2边内容相同，以此我们可以对之后的字符的回文做推断，减少计算次数
#     ^b#a#b#c#b#a#b#c#b#a#c#c#b#a$
#       <--------|-------->
#     000201060109
#
#
# 自动跳过几个不好解说的字符，到如下状态
#     ^b#a#b#c#b#a#b#c#b#a#c#c#b#a$
#       <--------|-------->
#             <0>|<0>
#     0002010601090
# 有左边'b'周围的回文长度可知有回文"#b#"，又因右边字符是和左边字符相同的，因而我们可以推断出下一个字符的回文长度是1，如下
#     ^b#a#b#c#b#a#b#c#b#a#c#c#b#a$
#       <--------|-------->
#             <0>|<0>
#     00020106010901
#
#
# 自动跳过几个如上相同的情况，到如下状态
#       <--------0-------->
#     ^b#a#b#c#b#a#b#c#b#a#c#c#b#a$
#     000201060109010
# 我们可以有'c'的回文长度6得到如下的
#     ^b#a#b#c#b#a#b#c#b#a#c#c#b#a$
#      <-----0----->
#       <--------|-------->
#     000201060109010
# 根据以上对称的原因我们做如下推测
#     ^b#a#b#c#b#a#b#c#b#a#c#c#b#a$
#      <-----0----->
#       <--------|-------->
#              <-----0----->
#     000201060109010
# 可以看到只有5个字符落在[9回文]的字符串中，另外多出一个因超出范围我们无法保证
#
# 由上所示过程我们得出结论
# 假设index_center的回文长度为p[index_center]
# 那么距离index_center长度为distance的下一个字符的回文长度，我们可以推测为
# p[index_center + distance] = min(p[index_center - distance], p[index_center] - distance)
# 具体解题算法如下，请进行参考理解

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)==0:
            return "";

        special_append = "^";
        for index in xrange(len(s)):
            special_append += s[index] + "#";
        special_append += "$";

        p = [0] * len(special_append);

        index_center = 0;
        for index in xrange(1, len(special_append) - 1):
            # 回文长度推断
            index_mirror = 2 * index_center - index;
            right_distance = index - index_center;
            if index_mirror >= 0:
                p[index] = min(p[index_mirror], p[index_center] - right_distance);
            else:
                p[index] = 0;

            # 根据推断结果，尝试扩展回文长度
            step = 1;
            while special_append[index - p[index] - step] == special_append[index + p[index] + step]:
                step += 1;

            # 扩展回文长度成功，说明已超过上一个[回文中心]的影响范围，切换新的[回文中心]
            if step != 1:
                index_center = index;
                p[index] += step - 1;

        max_p_value = 0;
        max_p_index = 1;
        for index in xrange(len(p)):
            if p[index] > max_p_value:
                max_p_value = p[index];
                max_p_index = index;

        # #max_p_index从扩展后数组的index转换为扩展前的index，再根据有无中心向2边进行扩展
        # if max_p_index % 2 == 0:
        #     return s[int((max_p_index - 1) / 2) - (max_p_value + 1) / 2 + 1 : int((max_p_index - 1)/2) + (max_p_value + 1) / 2 + 1];
        # else:
        #     return s[(max_p_index - 1) / 2 - max_p_value / 2 : (max_p_index - 1) / 2 + max_p_value / 2 + 1];

        #根据max_p_index和max_p_value获取在扩展后的index上的有效index，然后再转换为扩展前的
        return s[(max_p_index - max_p_value) / 2 : (max_p_index + max_p_value - 1) / 2 + 1];



t = Solution();
print t.longestPalindrome("babcbabcbaccba");